package nu.aing.P20140908;

import java.util.Arrays;

/**
 * KAGAK NGARTI !!! GW NYONTEK !!!
 * 
 * @author memekmaut@gmail.com
 */
public class SuffixArrayDiv2 {
    
    public static void main(String[] args) {
        SuffixArrayDiv2 obj = new SuffixArrayDiv2();
        System.out.println(obj.smallerOne("abca"));
        System.out.println(obj.smallerOne("bbbb"));
        System.out.println(obj.smallerOne("aaaa"));
        System.out.println(obj.smallerOne("examplesareveryweakthinktwicebeforesubmit"));
    }
    
    public String smallerOne(final String s) {
        final char[] chars = s.toCharArray();
        final int n = chars.length;
        final Wrap[] suffixArr = new Wrap[n];
        for(int i = 0; i < n; i++) {
            suffixArr[i] = new Wrap(s.substring(i), i);
        }
        Arrays.sort(suffixArr);
        
        final Wrap[] suffixArrB = new Wrap[n];
        String kontol = "";
        boolean isValid = false;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 'a' && chars[i] != 'a'; j++) {
                if(chars[i] == 'a') continue;
                chars[i]--;
                
                kontol = new String(chars);
                for(int k = 0; k < n; k++) {
                    suffixArrB[k] = new Wrap(kontol.substring(k), k);
                }
                Arrays.sort(suffixArrB);
                
                for(int l = 0; l < n; l++) {
                    if(suffixArr[l].equals(suffixArrB[l]) ) {
                        isValid = true;
                        break;
                    }
                }
                if(isValid) {
                    break;
                }
            }
        }
        if(isValid) {
            return "Exist";
        }
        
        return "Does not exist";
    }
    
    class Wrap implements Comparable<Wrap> {
        String s;
        int i;
        public Wrap(String s, int i) {
            this.s = s;
            this.i = i;
        }
        
        @Override
        public int compareTo(Wrap o) {
            return s.compareTo(o.s);
        }
        
        @Override
        public boolean equals(Object obj) {
            Wrap w = (Wrap) obj;
            return i == w.i;
        }
        
        @Override
        public String toString() {
            return String.format("(%s)(%s)", s, i);
        }
    }
}
